package com.fr.lintcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

public class Q186 {

	//重复的点怎么算
	/**
	 * @param points: an array of point
	 * @return: An integer
	 */
	public int maxPoints(Point[] points) {
		// write your code here
		if (points == null) {
			return 0;
		}
		if (points.length <= 2) {
			return points.length;
		}
		int max = 2;
		Map<Double, Map<Double, Integer>> map = new HashMap<>();
		Map<Double, Set<Double>> exsits = new HashMap<>();
		int length = points.length;
		for (int i = 0; i < length - 1; i++) {
			Map<Double, Set<Double>> exsitsTmp = new HashMap<>();
			for (int j = i + 1; j < length; j++) {
				Double a = null;
				Double b = null;
				int x = points[i].x - points[j].x;
				int y = points[i].y - points[j].y;
				if (x == 0) {
					b = (double) points[i].x;
				} else {
					a = y / (double) x;
					b = points[i].y - a * points[i].x;
				}
				Set<Double> bTmp = exsits.get(a);
				if (bTmp == null) {
					bTmp = new HashSet<>();
				}else if(bTmp.contains(b)){
					continue;
				}
				bTmp.add(b);
				exsitsTmp.put(a, bTmp);
				Map<Double, Integer> tmp = map.get(a);
				if (tmp == null) {
					tmp = new HashMap<>();
					map.put(a, tmp);
				}
				Integer count = tmp.get(b);
				if (count == null) {
					count = 1;
				}
				count++;
				tmp.put(b, count);
				if (max < count) {
					max = count;
				}
			}
			merge(exsits, exsitsTmp);
		}
		return max;
	}

	private void merge(Map<Double, Set<Double>> exsits, Map<Double, Set<Double>> exsitsTmp) {
		for(Map.Entry<Double, Set<Double>> entry : exsitsTmp.entrySet()) {
			Set<Double> tmp = exsits.get(entry.getKey());
			if(tmp == null) {
				exsits.put(entry.getKey(), entry.getValue());
			}else {
				tmp.addAll(entry.getValue());
			}
		}
	}

	class Point {
		int x;
		int y;

		Point() {
			x = 0;
			y = 0;
		}

		Point(int a, int b) {
			x = a;
			y = b;
		}
	}
	
	@Test
	public void testMaxPoints() {
//		Point[] ps = new Point[4];
//		[1,2],[3,6],[0,0],[1,3]
//		ps[0] = new Point(1,2);
//		ps[1] = new Point(3,6);
//		ps[2] = new Point(0,0);
//		ps[3] = new Point(1,3);
		int [][] t = {{-435,-347},{-435,-347},{609,613},{-348,-267},{-174,-107},{87,133},{-87,-27},{-609,-507},{435,453},{-870,-747},{-783,-667},{0,53},{-174,-107},{783,773},{-261,-187},{-609,-507},{-261,-187},{-87,-27},{87,133},{783,773},{-783,-667},{-609,-507},{-435,-347},{783,773},{-870,-747},{87,133},{87,133},{870,853},{696,693},{0,53},{174,213},{-783,-667},{-609,-507},{261,293},{435,453},{261,293},{435,453}};
		int length = t.length;
		Point[] ps = new Point[length];
		for(int i = 0; i < length; i ++) {
			ps[i] = new Point(t[i][0], t[i][1]);
		}
		int rs = maxPoints(ps);
		System.out.println(rs);
	}

}
